﻿// 0901train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
 (1+(2+3)*(3+(8+0))+1-2)这是一个简单的数学表达式
 今天不是计算它的值,而是比较它的括号匹配是否正确
前面这个式子可以简化为(()(()))这样的括号我们认为它是匹配正确的,
而((())这样的我们就说他是错误的
注意括号里面的表达式可能是错的,也可能有多个空格，只关心括号是否使用正确

输入描述
给出一行表达式(长度不超过 100)。

输出描述
如果匹配正确输出括号的对数，否则输出-1

输入
(1+(2+3)*(3+(8+0))+1-2)
输出
4
 */

class Solution01
{
public:
    int result = 0;
    bool is_verify = true;
    Solution01(string&oh_str)
    {
        vector<char>stack_vec;

        for (auto&oh_char:oh_str)
        {
            if (oh_char=='(')
            {
                stack_vec.push_back(')');
                result += 1;
            }
            else if (oh_char==')')
            {
                if (stack_vec.empty())
                {
                    is_verify = false;
                    break;
                }
                stack_vec.pop_back();
            }
        }

        if (!is_verify || !stack_vec.empty())
        {
            cout << -1;
            return;
        }
        cout << result;
    }
};


/*
 给出一个字符串s(仅含有小写英文字母和括号)。
请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果
注意，您的结果中不应包含任何括号

输入
(abcd)
输出
dcba

输入
(u(love)i)
输出
iloveu
先反转子字符串"love"，然后反转整个字符串

输入
(ed(et(oc))el)
输出
leetcode
先反转子字符串"oc"，接着反转"etco"，然后反转整个字符串


 */

class Solution02
{
public:
    Solution02(string&origin_str)
    {
        //左括号，判断curr_str是否为空，不为空压栈
        //右括号，
        //判断stack是否为空，不为空，弹出prev
        //反转curr_str,curr_str先进，prev晚进
        //"evol" "u"  
        //curr_str "i" prev "loveu"
        vector<string>stack_v;
        
        for (int i=0; i<origin_str.size(); i++)
        {
            char oh_char = origin_str[i];

            if (oh_char=='(')
            {
                stack_v.push_back("");
            }
            else if (oh_char==')')
            {
                string curr = stack_v.back();
                stack_v.pop_back();

                reverse(curr.begin(), curr.end());
                if (!stack_v.empty())
                {
                    stack_v.back() += curr;
                }
                else
                {
                    stack_v.push_back(curr);
                }
            }
            else
            {
                if (stack_v.empty()) stack_v.push_back("");
                stack_v.back() += oh_char;
            }
        }

        string result = stack_v.back();
        cout << result;
        //Solution02
    }
};

/*
 形如(OP P1 P2 …)，括号内元素由单个空格分割
 其中第一个元素 OP 为操作符，后续元素均为其参数，参数个数取决于操作符类型
注意：参数 P1, P2 也有可能是另外一个嵌套的(OP P1 P2 …)
当前 OP 类型为 add / sub / mul / div（全小写），分别代表整数的加减乘除法
简单起见，所有 OP 参数个数均为 2
举例：
- 输入：(mul 3 -7) 输出： -21 mul乘
- 输入：(add 1 2) 输出：3 add加
- 输入：(sub (mul 2 4) (div 9 3)) 输出：5 8-3=5
- 输入：(div 1 0) 输出：error div除
题目涉及数字均为整数，可能为负；不考虑 32 位溢出翻转，计算过程中也不会发生 32 位溢出翻转
除零错误时，输出 "error"，除法遇除不尽，向下取整，即 3 / 2 = 1

输入
输入为长度不超过 512 的字符串，用例保证了无语法错误

输出
输出计算结果或者"error"

输入
(div 12 (sub 45 45))
输出
error

输入
(add 1 (div -7 3))
输出
-2
 */
class Solution03
{
public:
    bool isChracter(char oh_char)
    {
        return oh_char >= 'a' && oh_char <= 'z';
    }

    bool isNum(char oh_char)
    {
        return oh_char >= '0' && oh_char <= '9';
    }

    int operateNum(string&op, int num1, int num2)
    {
        //add / sub / mul / div
        if (op=="add")
        {
            return num1 + num2;
        }
        else if (op=="sub")
        {
            return num1 - num2;
        }
        else if (op == "mul")
        {
            return num1 * num2;
        }
        else if (op=="div")
        {
	        if (num2==0)
	        {
                is_verify = false;
                return -1;
	        }
            double res = double(num1) / double(num2);
            return  floor(res);
        }

        //OperateNum
    }

    Solution03(string&origin_str)
    {
        //(div 12 (sub 45 45))
        int str_size = origin_str.size();
        vector<string>stack_op_v;
        vector<int>stack_num_v;

        string curr_op;
        int sign = 1;
        bool is_prev_num = false;
        int curr_num = 0;

        //1去最外层括号
        //2if(isChrater(oh_char)curr_op+=char
        //if(isNum(oh_char)curr_num=curr*10+curr_num
        //3左括号，stack_op_v.push_back(curr_op) stack_num_v.push_back(curr_num)
        //4右括号，取出1个op和2个num做运算再往里推

        for (int i=1; i< str_size; i++)
        {
            char curr_char = origin_str[i];

            if (isChracter(curr_char)) curr_op += curr_char;
            else if (isNum(curr_char))
            {
                curr_num = curr_num * 10 + curr_char - '0';
                is_prev_num = true;
            }
            else if (curr_char==' ')
            {
                if (!curr_op.empty())
                {
                    stack_op_v.push_back(curr_op);
                    curr_op = "";
                }
                if (is_prev_num)
                {
                    stack_num_v.push_back(curr_num * sign);
                    curr_num = 0;
                    sign = 1;
                    is_prev_num = false;
                }
            }
            else if (curr_char=='-')
            {
                sign = -1;
            }
            else if (curr_char==')')
            {
                if (is_prev_num)
                {
                    stack_num_v.push_back(curr_num*sign);
                    curr_num = 0;
                    sign = 1;
                    is_prev_num = false;
                }

                string compute_op = stack_op_v.back();
                stack_op_v.pop_back();

                int num2 = stack_num_v.back();
                stack_num_v.pop_back();

                int num1 = stack_num_v.back();
                stack_num_v.pop_back();

                int result = operateNum(compute_op, num1, num2);

                if (!is_verify)
                {
                    cout << "error";
                    return;
                }
                stack_num_v.push_back(result);
            }

        }

        cout << stack_num_v.back();
        //Solution03
    }
private:
    bool is_verify = true;
};


/*
 为了提升数据传输的效率，会对传输的报文进行压缩处理
输入一个压缩后的报文，请返回它解压后的原始报文
压缩规则：n[str]，表示方括号内部的 str 正好重复 n 次
注意 n 为正整数（0 < n <= 100），str只包含小写英文字母，不考虑异常情况

输入描述
输入压缩后的报文：
1）不考虑无效的输入，报文没有额外的空格，方括号总是符合格式要求的
2）原始报文不包含数字，所有的数字只表示重复的次数 n
例如不会出现像 5b 或 3[8] 的输入

输出描述
解压后的原始报文

输入
3[k]2[mn]
输出
kkkmnmn
k 重复3次，mn 重复2次，最终得到 kkkmnmn

输入
3[m2[c]]
输出
mccmccmcc
m2[c] 解压缩后为 mcc，重复三次为 mccmccmcc
 */
class Solution04
{
public:
    bool isChracter(char oh_char)
    {
        return oh_char >= 'a' && oh_char <= 'z';
    }

    bool isNum(char oh_char)
    {
        return oh_char >= '0' && oh_char <= '9';
    }
    Solution04(string&origin_str)
    {
        //3[m2[c]]
        //左括号，数字压栈，字符压栈
        //右括号，数字出栈，跟当前字符运算，拼到字符末尾

        vector<string>stack_str_v;
        vector<int>stack_num_v;

        int curr_num = 0;
        string curr_str;

        for (auto&oh_char:origin_str)
        {
            if (isNum(oh_char))
            {
                curr_num = curr_num * 10 + oh_char - '0';
            }
            else if (isChracter(oh_char))
            {
                curr_str += oh_char;
            }
            else if (oh_char=='[')
            {
                if (!curr_str.empty())
                {
                    stack_str_v.push_back(curr_str);
                    curr_str = "";
                }
                if (curr_num!=0)
                {
                    stack_num_v.push_back(curr_num);
                    curr_num = 0;
                }
            }
            else if (oh_char==']')
            {
	            //弹出数字跟curr_str做运算2
                int count = stack_num_v.back();
                stack_num_v.pop_back();

                string pre_str;
                if (!stack_str_v.empty())
                {
                    pre_str = stack_str_v.back();
                    stack_str_v.pop_back();
                }

                string new_str;
                while (count--)
                {
                    new_str += curr_str;
                }

                curr_str = pre_str + new_str;

                //else if (oh_char==']')
            }
        }

        
        cout << curr_str;
        //Solution04
    }
};


int main()
{
	{
        //3[k]2[mn]
        //3[m2[c]]
        string input = "2[2[dq3[3[a]4[v]5[u]6[p]]]9[io]]4[yodc]2[abc]40[zx]";
        //string input;
        //getline(cin, input);
        Solution04 solu(input);

        return 0;
	}
	{
        //(div 12 (sub 45 45))
        //string input = "(div 12 (sub 45 45))";
        string input;
        getline(cin, input);
        Solution03 solu(input);

        return 0;
	}
	{
        string input;
        getline(cin, input);
        Solution02 solu(input);
        return 0;
	}
    string input;
    getline(cin, input);
    Solution01 solu(input);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
